package 代码随想录_动态规划.基础题目;

/**
 * @author zx
 * @create 2022-05-22 20:41
 * 1.确定dp数组（dp table）以及下标的含义
 * dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
 * 2.确定递推公式
 *  可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
 *  dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
 * 3.dp数组如何初始化
 * p[0] dp[1] 就不应该初始化，也就是没有意义的数值。
 *  只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！
 * 4.确定遍历顺序
 *
 * 5.举例推导dp数组
 *
 */
public class 整数拆分_343 {
    public int integerBreak(int n) {
        //dp[i]为正整数i拆分结果的最大乘积
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3;i <= n;i++){
            for(int j = 1;j < i - 1;j++){
                //j*(i-j)：把i拆分为j和i-j两个数相乘
                //j*dp[i-j]：把i拆分成j和继续把(i-j)这个数拆分,取(i-j)拆分结果中的最大乘积与j相乘
                dp[i] = Math.max(dp[i],Math.max(j * (i - j),j * dp[i - j]));
            }
        }
        return dp[n];
    }
}
